import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    // 插入排序
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];//tmp是每次 要插入的牌
            int j = i - 1;

            for(; j >= 0; j--) {//对tmp 前面的元素进行循环
                if (array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
            //1.当j<0 循环结束时(tmp为最小) 赋值  j此时为-1, 给0下标赋值
            //2.当不满足if时,也赋值  j+1的位置是 上一次循环 array[j+1] = array[j]; 中 array[j]
            //已经有位置存放了, 所以此位置存放tmp
        }
    }

    // 希尔排序
    public static void shellSort(int[] array){
        int gap = array.length;
        while (gap > 1) {
            gap /= 2;
            shell(array,gap);
        }
    }
    public static void shell(int[] array,int gap) {
        //i每次加1, j则是i-gap 保证每组跟每组的进行比较
        for (int i = gap; i < array.length; i++) {//对每组进行插入排序,使每组都有序
            int tmp = array[i];
            int j = i - gap;

            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                }else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
    // 选择排序
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int tmp = i;//最小值下标
            for (int j = i+1; j < array.length; j++) {
                if (array[tmp] > array[j]) {
                    tmp = j;//找到最小值下标
                }
            }
            int tmpArr = array[i];//交换
            array[i] = array[tmp];
            array[tmp] = tmpArr;
        }
    }


    // 堆排序
    public static void heapSort(int[] array){
        // write code  here
        //创建大根堆
        createHeap(array);

        int end = array.length-1;//交换次数
        while (end > 0) {
            swap(array,0,end);//首位交换
            siftDown(array,0,end);//交换一次就调整一次
            end--;
        }
    }

    private static void createHeap(int[] array) {//大根堆创建
        for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {
            siftDown(array,parent,array.length);
        }
    }

    private static void siftDown(int[] array,int parent,int len) {//堆 向下调整
        int child = (2*parent)+1;
        while (child < len) {
            if(child + 1 < len && array[child] < array[child+1]) {
                child = child+1;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }
    public static void swap (int[] array,int left,int right) {
        int cmp = array[left];
        array[left] = array[right];
        array[right] = cmp;
    }

    // 冒泡排序
    public static void bubbleSort(int[] array){
        // write code  here
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] > array[j]) {
                    int tmp = array[i];
                    array[i] = array[j];
                    array[j] = tmp;
                }
            }
        }
    }

// 快速
    public static void quickSort(int[] array, int left, int right){
        // write code  here
        if (right - left < 1) {//只有一个元素时退出递归 递归结束条件
            return;
        }
        int div = quick(array, left, right);

        //左
        quickSort(array, left, div);

        //右
        quickSort(array, div+1, right);
    }
    public static int quick(int[] array, int l, int r) {//挖坑法,返回分好后的基准值下标
        int left = l;
        int right = r;
        int tmp = array[l];//先挖一个坑(这个坑是基准值),记录这个坑
        while (left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];//找到小的直接赋给前面的坑

            while(left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];//找到大的直接赋给后面的坑

            array[left] = tmp;//把基准值补上
        }
        return left;
    }
    // 归并排序---递归
    public static void mergeSort(int[] array){
        // write code  here
        mergeFun(array, 0, array.length-1);

    }
    //归并排序- 分解函数
    public static void mergeFun(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        //左右递归分解
        mergeFun(array, left, mid);
        mergeFun(array, mid+1, right);
        //分解完开始合并 合并的时候 排好序
        merge(array, left, mid, mid+1, right);

    }
    public static void merge(int[] array, int left, int leftEnd, int right, int rightEnd) {
        int s1 = left;
        int e1 = leftEnd;
        int s2 = right;
        int e2 = rightEnd;

        int[] arr = new int[rightEnd-left+1];
        int k = 0;

        //先让某一边排完 (让靠前的一边排到前面)
        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] > array[s2]) {
                arr[k++] = array[s2++];
            }else {
                arr[k++] = array[s1++];
            }
        }
        //把剩下的没排完的补到后面(剩下的肯定是较大的)
        while (s2 <= e2) {
            arr[k++] = array[s2++];
        }
        while (s1 <= e1) {
            arr[k++] = array[s1++];
        }

        //把整理好的数组赋给 原数组
        //注意1: 被赋值对象下标需要加left(因为这个函数不是执行一次,之前每次递归返回都要执行)
        //注意2: 赋值k次,上面赋值了几次 k都会自增
        for (int i = 0; i < k; i++) {
            array[i+left] = arr[i];
        }

    }
    //非递归 归并
    public static void mergeSort2(int[] array) {
        int  gap = 1;
        //最外层循环 控制组数
        while (gap < array.length) {
            //每一组进行排序
            for (int i = 0; i < array.length; i = i+2*gap) {//每次按照2*gap 遍历数组分成多组
                int left = i;
                int mid = left + gap-1;
                if(mid >= array.length) {//防止超过
                    mid = array.length-1;
                }
                int right = mid+gap;
                if(right >= array.length) {//防止超过
                    right = array.length-1;
                }
                merge(array,left,mid,mid+1,right);//分成的多组进行合并并排序
            }
            gap *= 2;//gap每次扩大一倍,这样越来越大,模拟归并
        }
    }
    // 计数排序
    public static void countSort(int[] array){

        //求最值 确定范围
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if(max < array[i]) {
                max = array[i];
            }
            if(min > array[i]) {
                min = array[i];
            }
        }
        //创建数组
        int[] cont = new int[max-min+1];

        //遍历原数组
        for (int i = 0; i < array.length; i++) {
            cont[array[i] - min]++;
        }

        //遍历cont 赋值给原数组
        int k = 0;
        for (int i = 0; i < cont.length; i++) {
            if (cont[i] >= 1) {
                int tmp = cont[i];
                while (tmp-- > 0) {
                    array[k++] = i + min;
                }
            }
        }


    }
    public static void main(String[] args) {
        int[] array = {33,2,78,33,1,67,54,12,0};
        //insertSort(array);
        //shellSort(array);
        //selectSort(array);
        //heapSort(array);
        //bubbleSort(array);
        //quickSort(array,0, array.length - 1);
        //mergeSort(array);
        //mergeSort2(array);
        countSort(array);
        for (int t:array) {
            System.out.print(t+" ");
        }
    }
}